<?php


namespace XiaoGuai\DataStructure\Queue\SequentialQueue;


use XiaoGuai\DataStructure\Queue\QueueInterface;

/**
 * 循环队列
 * Class SequentialQueue
 * @package XiaoGuai\DataStructure\Queue\SequentialQueue
 */
class SequentialQueue implements QueueInterface
{

    /**
     * 队列的容量,保留队头一个元素不用
     */
    const MAX_SIZE = 100;

    /**
     * @var array 队列的元素
     */
    protected $elements = [];

    /**
     * @var int 头指针, front可以追上rear,将元素全部推出
     */
    protected $front = 0;

    /**
     * @var int 尾指针, rear到front前面保留一个元素
     */
    protected $rear = 0;

    /**
     * 构造一个空队列
     * QueueInterface constructor.
     */
    public function __construct()
    {
        $this->elements = [];
        $this->front = 0;
        $this->rear = 0;
    }

    /**
     * 队列元素是否为空
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->front == $this->rear;
    }

    /**
     * 队列元素长度
     * @return int
     */
    public function length(): int
    {
        return ($this->front - $this->rear + self::MAX_SIZE) % self::MAX_SIZE;
    }

    /**
     * 队列顶部元素
     * @return mixed
     */
    public function top()
    {
        if ($this->front == $this->rear) {
            throw new \Exception('overflow');
        }
        return $this->elements[$this->front];
    }

    /**
     * 入队
     * @param $element
     * @return bool
     */
    public function enqueue($element): bool
    {
        // 判断是否会溢出
        if (($this->rear + 1) % self::MAX_SIZE == $this->front) {
            return false;
        }

        $this->elements[$this->rear] = $element;
        $this->rear = ($this->rear + 1) % self::MAX_SIZE;
        return true;
    }

    /**
     * 出队
     * @return mixed
     */
    public function dequeue()
    {
        // 判断是否会溢出
        if (($this->front) % self::MAX_SIZE  == $this->rear) {
            throw new \Exception('overflow');
        }
        $element = $this->elements[$this->front];
        $this->front = $this->front % self::MAX_SIZE;
        return $element;
    }
}